package Hot_100;
import org.junit.Test;

public class T33_search {
    @Test
    public void test() {
        // int []num = {4,5,6,7,0,1,2};
        // int []num = {1,3};
        // int []num = {5,1,3};
        int []num={4,5,6,7,8,9,1,2,3};
        System.out.println(search(num, 1));
    }

    /*
        其实这个题就是二分查找的变形，由于题目给定的参数里没有下标值start,end的，所以不能使用递归求解
        因为是将原本的有序数组中的一部分放到前面，所以在mid的左半区或右半区可能出现不是有序的情况
        如果nums[mid]>nums[begin]，则说明左区是有序，右区可能是有序也可能是无序的;
        如果nums[mid]<nums[begin],则说明左区是无序的，右半区有序
    */
    //  要理清逻辑，不然会出现很多bug
    public int search(int[] nums, int target) {
        int start, mid, end;
        start=0;
        end=nums.length-1;
        mid=(start+end)/2;

        while (start < end) {

            if (nums[mid] == target) {        //判断是否相等
                return mid;
            }

            if (nums[start] <= nums[mid]) {   //左区域有序   注意是小于等于,不然有bug，参考测试案例 [3,1] 1
                if (target > nums[mid]||target<nums[start]) { //大于左半区的最大值or小于左半区的最小值，说明target应该在右半区
                    start=mid+1;
                    mid=(start+end)/2;
                }
                else {  //如果target在左半区
                    end = mid - 1;
                    mid = (start + end) / 2;
                }
            }
            else {     //右半区有序
                if (target < nums[mid]||target>nums[end]){
                    end=mid-1;
                    mid = (start + end) / 2;
                }else{
                    start = mid + 1;
                    mid = (start + end) / 2;
                }
            }
        }

        if (start == end && nums[mid] == target) {
            return mid;
        }

        return -1;
    }


    public int search_2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid=(start+end)/2;

            if (nums[mid] == target) {
                return mid;
            }
            //前半部分有序,注意此处用小于等于
            if (nums[start] <= nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {   //target在前半部分
                    end = mid - 1;
                } else {   //target在后半部分
                    start = mid + 1;
                }
            } else {
                if (target <= nums[end] && target > nums[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}
